package leetcode.codetop.腾讯;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/4 10:32
 * @description：https://leetcode-cn.com/problems/valid-parenthesis-string/
 */
public class 有效的括号字符串 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"));
    }

    /*
    // 栈
    class Solution {
        public boolean checkValidString(String s) {
            Stack<Integer> leftStack = new Stack<>();
            Stack<Integer> asteriskStack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char aChar = s.charAt(i);
                if (aChar == '(') {
                    leftStack.push(i);
                } else if (aChar == '*') {
                    asteriskStack.push(i);
                } else if (aChar == ')') {
                    if (!leftStack.isEmpty()) {
                        leftStack.pop();
                    } else if (!asteriskStack.isEmpty()) {
                        asteriskStack.pop();
                    } else
                        return false;
                }
            }
            while (!leftStack.isEmpty()) {
                if (asteriskStack.isEmpty()) return false;
                Integer left_index = leftStack.pop();
                Integer asterisk_index = asteriskStack.pop();
                if (left_index > asterisk_index) {
                    return false;
                }
            }
            return true;
        }
    }
     */

    // 贪心
    class Solution {
        public boolean checkValidString(String s) {
            // 维护未匹配左括号的最大值和最小值
            int minCount = 0, maxCount = 0;
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
                // 最大值和最小值都不能为负，最大值为负return false
                if (aChar == '(') { // 匹配左括号，最大最小值++
                    maxCount++;
                    minCount++;
                } else if (aChar == ')') { // 匹配到右括号，最大值最小值--
                    minCount = Math.max(minCount - 1, 0);
                    maxCount--;
                    if (maxCount < 0) return false;
                } else { // 匹配到星号，最大值 + 1，最小值 - 1
                    maxCount++;
                    minCount = Math.max(minCount - 1, 0);
                }
            }
            return minCount == 0;
        }
    }
}
